package com.czk.tree;

import lombok.Getter;
import lombok.Setter;

/**
 * @Author:ChenZhangKun
 * @Date: 2020/7/5 14:14
 */
public class BinaryTreeDemo {
    public static void main(String[] args) {
        // 创建二叉树
        Node node4 = new Node(4, null, null);
        Node node5 = new Node(5, null, null);
        Node node2 = new Node(2, node4, node5);
        Node node6 = new Node(6, null, null);
        Node node7 = new Node(7, null, null);
        Node node3 = new Node(3, node6, node7);
        Node node1 = new Node(1, node2, node3);
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.setNode(node1);
        // 前序遍历
        binaryTree.preTraverse();
        // 中序遍历
        System.out.println();
        binaryTree.inOrderTraverse();
        // 后续遍历
        System.out.println();
        binaryTree.postTraverse();
        // 前序查找
        System.out.println();
        System.out.println(binaryTree.getByPreTraverse(3));
        // 中需查找
        System.out.println(binaryTree.getByInOrderTraverse(3));
        // 后续遍历
        System.out.println(binaryTree.getByPostTraverse(3));

        // 删除3
        binaryTree.delete(3);
        binaryTree.preTraverse();
    }
}

class BinaryTree {
    private Node node;

    public void setNode(Node node) {
        this.node = node;
    }
    // 删除节点
    public void delete(int name){
        if (node!=null){
            if (node.getName()==name){
                node=null;
            }else {
                node.delete(name);
            }
        }else {
            System.out.println("主节点为空");
            return;
        }
    }
    // 前序遍历
    public void preTraverse() {
        if (node != null) {
            node.preTraverse();
        }
    }

    // 中序遍历
    public void inOrderTraverse() {
        if (node != null) {
            node.inOrderTraverse();
        }
    }

    // 后续遍历
    public void postTraverse() {
        if (node != null) {
            node.postTraverse();
        }
    }
    // 前序查找
    public Node getByPreTraverse(int name){
        return node.getByPreTraverse(name);
    }
    // 中序查找
    public Node getByPostTraverse(int name){
        return node.getByPostTraverse(name);
    }
    // 前序查找
    public Node getByInOrderTraverse(int name){
        return node.getByInOrderTraverse(name);
    }
}

// 创建节点对象
@Getter
@Setter
class Node {
    // 名字
    private Integer name;
    // 左节点
    private Node left;
    // 右节点
    private Node right;

    public Node(Integer name, Node left, Node right) {
        this.name = name;
        this.left = left;
        this.right = right;
    }

    /**
     * 删除节点
     * 使用递归操作
     * @param name
     */
    public void delete(int name){
        // 左子节点是否要删除
        if (this.getLeft()!=null&&this.getLeft().getName()==name){
            // 置为空
            this.setLeft(null);
            return;
        }
        // 右子节点删除
        if (this.getRight()!=null&&this.getRight().getName()==name){
            // 值为空
            this.setRight(null);
            return;

        }
        // 向左子树递归
        if (this.getLeft()!=null){
            this.getLeft().delete(name);
        }
        // 向右子树递归
        if (this.getRight()!=null){
            this.getRight().delete(name);
        }

    }
    @Override
    public String toString() {
        return  name+"";
    }

    // 先续遍历
    public void preTraverse() {

        System.out.print(this + " ");
        if (this.getLeft() != null) {
            this.getLeft().preTraverse();
        }
        if (this.getRight() != null) {
            this.getRight().preTraverse();

        }

    }

    // 中序遍历
    public void inOrderTraverse() {
        if (this.getLeft() != null) {
            this.getLeft().inOrderTraverse();
        }
        System.out.print(this + " ");
        if (this.getRight() != null) {
            this.getRight().inOrderTraverse();
        }
    }

    // 后续遍历
    public void postTraverse() {
        if (this.getLeft() != null) {
            this.getLeft().postTraverse();
        }
        if (this.getRight() != null) {
            this.getRight().postTraverse();
        }
        System.out.print(this + " ");
    }
    // 前序遍历查找
    public Node getByPreTraverse(int name){
        // 先与当前节点比较，找到则返回
        System.out.println("进入前序查找");
        if (this.getName()==name){
            return this;
        }
        // 定义变量接收数据
        Node result=null;
        // 向左递归
        if (this.getLeft()!=null){
            result=this.getLeft().getByPreTraverse(name);
        }
        // 不等于空则返回结果
        if (result!=null){
            return result;
        }
        // 向右递归
        if (this.getRight()!=null){
            result=this.getRight().getByPreTraverse(name);
        }
        // 返回结果
        if (result!=null){
            return result;
        }
        return null;
    }
    // 中序查找
    public Node getByInOrderTraverse(int name){
        Node result=null;
        // 先左递归
        if (this.getLeft()!=null){
            result=this.getLeft().getByInOrderTraverse(name);
        }
        // 与当前节点比较
        if (result!=null){
            return result;
        }
        System.out.println("进入中序查找");
        if (this.getName()==name){
            return this;
        }
        // 后续递归
        if (this.getRight()!=null){
            result=this.getRight().getByInOrderTraverse(name);
        }
        return result;
    }
    // 后续递归查找
    public Node getByPostTraverse(int name){
        // 左递归
        Node result=null;
        if (this.getLeft()!=null){
            result=this.getLeft().getByPostTraverse(name);
        }
        if (result!=null){
            return result;
        }
        // 右递归
        if (this.getRight()!=null){
            result=this.getRight().getByPostTraverse(name);
        }
        if (result!=null){
            return result;
        }
        System.out.println("进入后续查找");
        // 与当前节点比较
        if (this.getName()==name){
            return this;
        }
        return null;
    }
}
